In devices for queue scheduling, such as routers or switches, service data packets to be sent need to be scheduled according to a certain rule, enabling each queue to obtain a fair scheduling opportunity, so that data of the queues can be sent uniformly. A conventional method adopts a weighted fair queue (WFQ). Specifically, the service data packets to be sent form queues at an input end of a scheduling device to wait for scheduling. First, an initial value (such as 0) of a response credit is preset for each queue participating in the scheduling. When a data packet passes through a queue, the response credit of the queue is accumulated correspondingly. For a single queue, the greater the number of bytes of the data packet passing through the queue is, the greater the accumulated response credit is. At the same time, a weight ratio is predefined for each queue, and the weight ratio reflects a priority of each queue, so that the response credit accumulated for a queue with a high priority is small when the data packet with the same number of bytes passes through the queue, while the response credit accumulated for a queue with a low priority is great when the data packet with the same number of bytes pass through the queue. In a queue scheduling process, a comparison operation is always performed on all the response credits, and a queue with the smallest response credit is selected and then scheduled; at the same time, the response credit is accumulated for the queue. In this way, queues are uniformly scheduled and a frequency of scheduling each queue is determined according to the predefined weight ratio. However, the response credits need to be compared with each other during selection of the to-be-scheduled queue, and to prevent the accumulated response credit from overflowing, all the response credits need to be cut down periodically and uniformly, resulting in a large amount of comparison and subtraction computations performed by the scheduling device; however, because the computing capability of the scheduling device is limited, a large number of input queues cannot be processed at the same time, and the complex operation greatly reduces the rate of sending the data packets and limits output bandwidth.
In order to process a large number of input queues at the same time and increase the rate of sending the data packets, in the prior art, another queue scheduling method is provided, which adopts a modified deficit round robin (MDRR). The method is specifically as follows: taking turns to give a scheduling opportunity to each queue participating in the scheduling; after one queue is scheduled once, scheduling a next adjacent queue; and performing a round robin in the same manner. Such a round robin manner does not need complex comparison and subtraction operations, thereby increasing the rate of scheduling and sending the data packets; moreover, a scheduler is able to support a large number of input queues without needing a strong computing capability. However, in this round robin manner, one queue is merely scheduled once, and the next queue is not scheduled until the queue sends all data allowed to be sent. The queue with a large weight is allowed to send a large amount of data in a single scheduling process. When the weights differ a lot between queues, and when it is a turn of a queue with a large weight to send service data, the data amount allowed to be sent is large, and a queue with a small weight is put aside for a long time; while a queue with a small weight is allowed to send a small amount of data in a single scheduling process, so other queues merely need to wait for a short time; as a result, queues cannot uniformly send the service data.
In the process of implementing the above queue scheduling, the inventors find that the prior art at least has the following problem: queues can uniformly send the service data through the WFQ, but the comparison between the response credits makes the operation complex, which results in that a large number of input queues cannot be processed. The MDRR can support a large number of input queues, but when queues are scheduled, the amounts of data allowed to be sent differ a lot, which results in that queues cannot uniformly send the service data.